package mock_or_enum;

public class 满足三条件之一需改变的最少字符数_1737{

    public static int minCharacters(String a, String b) {
        int al = a.length();
        int bl = b.length();
        int[] aCnt = new int[26];
        int[] bCnt = new int[26];
        for(char c : a.toCharArray()) {
            aCnt[c - 'a'] ++;
        }
        for(char c : b.toCharArray()) {
            bCnt[c - 'a'] ++;
        }
        int[] leCharA = new int[26]; // 字符串a中 小于等于 'a' + i 的字符数量  该前缀和只用来求和 不用做求区间和
        int[] leCharB = new int[26]; // 字符串b中 小于等于 'a' + i 的字符数量
        for (int i = 0; i < 26; i++) {
            leCharA[i] = i == 0 ? aCnt[0] : leCharA[i - 1] + aCnt[i];
        }
        for (int i = 0; i < 26; i++) {
            leCharB[i] = i == 0 ? bCnt[0] : leCharB[i - 1] + bCnt[i];
        }
        int res = Integer.MAX_VALUE;
        // 逐个分界点字母c尝试
        for(int i = 0; i< 26; i++) {
            if( i < 25) { // i == 25时  不可能有  修改次数 使得任意字母大于z 测试中的结果将在第32行等于 1  实际上至少应该调整两次
                // a <= c 需要的修改次数 al - leCharA[i]   b > c 需要的修改次数 leCharB[i]
                res = Math.min(res,al - leCharA[i] + leCharB[i]);
                // b <= c 需要的修改次数 bl - leCharB[i]   a > c 需要的修改次数 leCharA[i]
                res = Math.min(res, leCharA[i] + bl - leCharB[i]);
            }
            res = Math.min(res, al - aCnt[i] + bl - bCnt[i]);  // a 改成全为c 需要的修改次数  + b 改成全为c 需要的修改次数
        }
        return res;
    }


    public static void main(String[] args) {
        System.out.println(minCharacters("aba", "caa"));
    }
}

